package com.code.test.second.dp;

/**
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
 *
 * 121. 买卖股票的最佳时机
 * 只能买入一次，卖出一次
 *
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 *
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 */
public class SCode121 {

    public int maxProfit(int[] prices) {

        /**
         * dp[i][0..1]
         * dp[i][0] 表示 第i天持有股票所得的现金 （持有，表示今天买入 或者 之前就买入）
         * dp[i][1] 表示 第i天不持有股票所得的现金 （不持有，表示今天卖出或者 之前就卖出）
         *
         * dp[i][0] = max(dp[i-1][0] , -prices[i]);
         *
         * 第i天不持有，是i-1天持有+今天卖出prices[i] | 或者i-1天不持有
         * dp[i][1] = max(dp[i-1][1], dp[i-1][0]+ prices[i]);
         *
         * 初始化：
         */
        int len = prices.length;
        int[][] dp = new int[len][2];

        // 第0天持有，即表示prices[0]现金花掉了，-prices[i]
        dp[0][0] = -prices[0];
        // 第0天不持有股票，也就是现金为0
        dp[0][1] = 0;

        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }

    /**
     * 贪心算法
     */
    public int maxProfitGreedy(int[] prices) {

        int low = Integer.MAX_VALUE;
        int ret = 0;
        for (int i = 0; i < prices.length; i++) {
            // 取最左最小价格
            low = Math.min(low, prices[i]);
            // 直接取最大区间利润
            ret = Math.max(ret, prices[i] - low);
        }
        return ret;
    }
}
